/*
 * com.future CO.,ltd.
 */

package com.future;

import com.future.util.TreeNode;

/**
 * Description: 222. ��ȫ�������Ľڵ����(��ˢ���14)
 * ��ȫ������ �Ķ������£�����ȫ�������У�������ײ�ڵ����û�����⣬����ÿ��ڵ������ﵽ���ֵ��
 * ����������һ��Ľڵ㶼�����ڸò�����ߵ�����λ�á�����ײ�Ϊ�� h �㣬��ò���� 1~2h���ڵ㡣
 * <p>
 * ʾ�� 1��
 * ���룺root = [1,2,3,4,5,6]
 * �����6
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/count-complete-tree-nodes
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/4/28:23:44
 */
public class Solution_222 {

    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(3);
        head.left.left = new TreeNode(4);
        head.left.right = new TreeNode(5);
        //head.right.left = new TreeNode(6);
       /* head.right.right = new TreeNode(7);
        head.left.left.left = new TreeNode(8);*/
        System.out.println(countNodes(head));
    }

    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int ans = process(root, 1, mostLeftHeight(root));
        return ans;
    }

    /**
     * ע�⣺���������ļ��㹫ʽ��2^(n-1)
     *
     * @param root
     * @param curLevel
     * @param h
     * @return
     */
    private static int process(TreeNode root, int curLevel, int h) {
        if (curLevel == h) {
            return 1;
        }
        // ����������߶�
        int curLeftH = mostLeftHeight(root.left);
        // ����������߶�
        int curRightH = mostLeftHeight(root.right);
        if (curLeftH > curRightH) {
            // �������߶ȴ����������߶ȣ���˵������������������
            //return process(root.left, curLevel + 1, h) + (1 << (curLeftH - 1));
            return process(root.left, curLevel + 1, h) + (int) Math.pow(2d, curRightH);
        } else {
            // �������߶ȵ����������߶ȣ�˵������������������
            //return process(root.right, curLevel + 1, h) + (1 << (curLeftH));
            return process(root.right, curLevel + 1, h) + (int) Math.pow(2d, curLeftH);
        }
    }

    /**
     * �ҵ�root�ڵ�����ڵ�ĸ߶�
     *
     * @param root
     * @return
     */
    private static int mostLeftHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int height = 0;
        TreeNode op = root;
        while (op != null) {
            height++;
            op = op.left;
        }
        return height;
    }
}
